#define _CRT_SECURE_NO_WARNINGS
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//int search(int x,int y)
//{
//	int l = 1, r = n;
//	while (l<r)
//	{
//		int m = (l + r) / 2;
//		if (a[m] >= x) r = m;
//		else l = m + 1;
//	}
//	if (a[l] <x) return 0;
//	int tmp = l;
//	l = 1, r = n;
//	while (l < r)
//	{
//		int m = (l + r+1) / 2;
//		if (a[m] <= y) l = m;
//		else r = m-1;
//	}
//	if (a[l]> y) return 0;
//	return l-tmp+1;
//}
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++) cin >>a[i];
//	int q; cin >> q;
//	while (q--)
//	{
//		int x, y; cin >> x >> y;
//		cout << search(x,y)<< endl;
//	}
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 2e5 + 10;
//int a[N];
//int main()
//{
//	int n, c; cin >> n >> c;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	sort(a + 1, a + n + 1);
//	long long ret = 0;
//	for (int i = 2; i <= n; i++)
//	{
//		long long tmp = a[i] - c;
//		ret += upper_bound(a + 1, a + i, tmp) - lower_bound(a + 1, a +i, tmp);
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 110;
//int f[N];
//int n;
//int main()
//{
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		f[i] = f[i - 1] + x;
//	}
//	int m; cin >> m;
//	while (m--)
//	{
//		int l, r; cin >> l >> r;
//		cout << f[r] - f[l - 1] << endl;
//	}
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int f[N];
//int n,p;
//int main()
//{
//	cin >> n >> p;
//	for (int i = 1; i <= n; i++)
//	{
//		int x; cin >> x;
//		f[i]+=x;
//		f[i + 1] -= x;
//	}
//	for (int i = 1; i <= p; i++)
//	{
//		int l, r,x; cin >> l >> r>>x;
//		f[l] += x;
//		f[r + 1] -= x;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		f[i] = f[i - 1] + f[i];
//		cout << f[i] << " ";
//	}
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e3 + 10;
//long long f[N][N];
//int n, m,c;
//int main()
//{
//	cin >> n >> m >> c;
//	long long ret = -1e18;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			int x; cin >> x;
//			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] +x;
//		}
//	}
//	int l=1, r=1;
//	for (int i = c; i <= n; i++)
//	{
//		for (int j = c; j <= m; j++)
//		{
//			int x = i - c + 1, y = j - c + 1;
//			long long tmp = f[i][j] - f[x-1][j] - f[i][y-1] + f[x-1][y-1];
//			if (ret < tmp)
//			{
//				l = x, r = y;
//				ret = tmp;
//			}
//		}
//	}
//	cout << l << " "<<r<<endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e3 + 10;
//int f[N][N];
//int n, m;
//int main()
//{
//	cin >> n >> m;
//	while (m--)
//	{
//		int x1, y1, x2, y2;
//		cin>> x1>> y1>> x2>> y2;
//		f[x1][y1]++;
//		f[x1][y2 + 1]--;
//		f[x2+1][y1]--;
//		f[x2+1][y2+1]++;
//	}
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= n; j++)
//		{
//			f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + f[i][j];
//			cout << f[i][j] << " ";
//		}
//		cout << endl;
//	}
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e3 + 10;
//int f[N][N];
//int n, m,q;
//int main()
//{
//	cin >> n >> m >> q;
//	for (int i = 1; i <= n; i++)
//	{
//		for (int j = 1; j <= m; j++)
//		{
//			int x; cin >> x;
//			f[i][j] = f[i][j - 1] + f[i - 1][j] - f[i - 1][j - 1] + x;
//		}
//	}
//	while(q--)
//	{
//		int x1, y1, x2, y2;
//		cin >> x1 >> y1 >> x2 >> y2;
//		int tmp = f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
//		cout << tmp << endl;
//	}
//	return 0;
//}
//#include<iostream>
//#include<algorithm>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int main()
//{
//	int m, n; cin >> m >> n;
//	for(int i=1;i<=m;i++) cin>>a[i];
//	sort(a + 1, a + m + 1);
//	long long ret = 0;
//	a[0] = -1e7;
//	while (n--)
//	{
//		int x; cin >> x;
//		auto it = lower_bound(a+1,a+m+1,x);
//		ret += min(abs(*it - x), abs(*(it - 1) - x));
//	}
//	cout << ret << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//typedef long long LL;
//const int N = 1e5 + 10;
//int a[N];
//int main()
//{
//	int n, k; cin >> n >> k;
//	LL sum=0;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//		sum += a[i];
//	}
//	sum /= k;
//	int t = 0,p;
//	for(int i = sum; i > 0; i--)
//	{
//		t = 0;
//		for (int j = 1; j <= n; j++)
//		{
//			t += a[j] / i;
//		}
//		if (t >= k)
//		{
//			p = i;
//			break;
//		}
//	}
//	cout << p << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 1e5 + 10;
//int a[N];
//int n;
//int cal(int x)
//{
//	int t = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		t += a[i] / x;
//	}
//	return t;
//}
//int main()
//{
//	int k,ma=0; cin >> n >> k;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> a[i];
//		ma = max(ma, a[i]);
//	}
//	int l = 0, r = ma;
//	while (l < r)
//	{
//		int m = (l + r+1) / 2;
//		if (cal(m) >= k) l = m;
//		else r = m - 1;
//	}
//	cout << l << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//typedef long long LL;
//const int N = 1e6 + 10;
//int a[N];
//int n, m;
//LL cal(int x)
//{
//	LL sum = 0;
//	for (int i = 1; i <= n; i++)
//	{
//		if(a[i]>x) sum += a[i] - x;
//	}
//	return sum;
//}
//int main()
//{
//	cin >> n >> m;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	LL l = 0, r = 4e5 + 10;
//	while (l < r)
//	{
//		int t = (l + r+1) / 2;
//		if (cal(t) >= m) l = t;
//		else r = t - 1;
//	}
//	cout << l << endl;
//	return 0;
//}
//#include<iostream>
//using namespace std;
//const int N = 5e4 + 10;
//int a[N];
//int t, n, m;
//int cal(int x)
//{
//	int l1 = 0, r1 = 1,cnt=0;
//	while (r1 <= n)
//	{
//		if (a[r1] - a[l1] < x) cnt++;
//		else
//		{
//			l1 = r1;
//		}
//		r1++;
//	}
//	return cnt;
//}
//int main()
//{
//	cin >> t >> n >> m;
//	for (int i = 1; i <= n; i++) cin >> a[i];
//	a[n + 1] = t;
//	n++;
//	int l = 1, r = t;
//	while (l < r)
//	{
//		int mid = (l + r+1) / 2;
//		if (cal(mid) <= m) l = mid;
//		else r = mid - 1;
//	}
//	cout << l << endl;
//	return 0;
//}